package ch.ethz.fcl.metrobuzz.algorithm.cluster.kmean;

import ch.ethz.fcl.metrobuzz.algorithm.sort.heapsort.HeapSort;
import ch.ethz.fcl.metrobuzz.algorithm.sort.heapsort.HeapSortData;
import ch.ethz.fcl.metrobuzz.scene.singapore.Arc;
import ch.ethz.fcl.metrobuzz.scene.singapore.RoadNetwork;
import ch.ethz.fcl.metrobuzz.spatialindex.object2d.Point2D;
import ch.ethz.fcl.metrobuzz.tools.MBTools;

public class KMean {
	private RoadNetwork rn;
	private int num;
	int[] init_index;

	private final int bus = 5507; // 0 - 5507 arcs are bus lanes

	// private final int mrt = 5553; // 5508 - 5553 arcs are mrt lanes

	public KMean(RoadNetwork rn) {
		this.rn = rn;
	}

	public ArcCluster[] execute(int num) {
		if (num <= 0)
			num = 1;
		this.num = num;
		init_index = new int[num];

		initIndex();

		ArcCluster[] clusters = new ArcCluster[num];

		clusters = evaluate(init_index, getClusters(init_index));

		// check if any cluster not satisfying
//		boolean recal = false;
//		for (int i = 0; i < num; i++)
//			if (clusters[i].getArcs().size() == 0) {
//				recal = true;
//				break;
//			}
//		// if have, regenerate
//		if (recal)
//			return execute(num);

		return clusters;
	}

	private ArcCluster[] getClusters(int[] index) {
		ArcCluster[] clusters = new ArcCluster[num];
		for (int i = 0; i < clusters.length; i++)
			clusters[i] = new ArcCluster(i);

		MBTools.print(index, false);
		float[][] distance = new float[num][bus];
		for (int i = 0; i < num; i++) {
			distance[i] = rn.arcDistance[index[i]];
		}

		for (int i = 0; i < bus; i++) {
			float min_distance = Float.MAX_VALUE;
			int cluster = -1;
			for (int j = 0; j < num; j++)
				if (distance[j][i] < min_distance) {
					cluster = j;
					min_distance = distance[j][i];
				}
			rn.getArcs().get(i).setCalculatedClusternumber(cluster);
			if (cluster != -1)
				clusters[cluster].addArc(rn.getArcs().get(i));
		}

		for (int i = 0; i < clusters.length; i++)
			clusters[i].calculateCentroid();

		return clusters;
	}

	/**
	 * K-means++ algorithm as proposed in
	 * http://en.wikipedia.org/wiki/K-means%2B%2B to choose the initial k points
	 */
	private void initIndex() {
		// randomly choose first center
		init_index[0] = Math.round((float) Math.random() * bus);

		for (int i = 1; i < num; i++) {
			// for all arcs, compute nearest distances to arc that has already
			// been chosen
			float nearest_dist[] = new float[bus];
			for (int k = 0; k < bus; k++) {
				nearest_dist[k] = Float.MAX_VALUE;
			}
			for (int j = 0; j < i; j++) {
				float[] distance_j = rn.arcDistance[init_index[j]];
				for (int k = 0; k < bus; k++)
					if (distance_j[k] < nearest_dist[k])
						nearest_dist[k] = distance_j[k];
			}

			// generate probability of each arc for to be next chosen
			HeapSortData[] probability = new HeapSortData[bus];
			for (int j = 0; j < bus; j++)
				probability[j] = new HeapSortData((float) Math.random()
						* nearest_dist[j] * nearest_dist[j], j);
			HeapSort.sort(probability);

			init_index[i] = probability[bus - 1].getIndex();
		}
	}

	private ArcCluster[] evaluate(int[] index, ArcCluster[] cluster) {
		ArcCluster[] oldClusters = cluster;
		int[] newIndex = newIndex(oldClusters);
		ArcCluster[] newClusters = getClusters(newIndex);

		float pre_shift = Float.MAX_VALUE;
		float new_shift = shift(newClusters, oldClusters);

		int count = 0;
		while (new_shift > 0.01f && Math.abs(new_shift - pre_shift) > 0.001f
				&& count < 100) { // if loop too many time, just terminate
									// through result not satisfying
			pre_shift = new_shift;
			oldClusters = newClusters;

			newIndex = newIndex(oldClusters);
			newClusters = getClusters(newIndex);

			new_shift = shift(newClusters, oldClusters);

			count++;
			MBTools.debug("shift " + new_shift, false);
		}

		return newClusters;
	}

	private int[] newIndex(ArcCluster[] clusters) {
		float[] mid_x = new float[clusters.length];
		float[] mid_y = new float[clusters.length];

		for (int i = 0; i < clusters.length; i++) {
			Point2D centroid = clusters[i].getCentroidPoint();
			mid_x[i] = centroid.getX();
			mid_y[i] = centroid.getY();
		}
		return getIndex(mid_x, mid_y);
	}

	private int[] getIndex(float[] mid_x, float[] mid_y) {
		int[] newIndex = new int[mid_x.length];
		for (int i = 0; i < mid_x.length; i++) {
			float min_dist = Float.MAX_VALUE;
			for (int j = 0; j < rn.getArcs().size(); j++) {
				Arc arc = rn.getArcs().get(j);
				float dist = arc.distance(mid_x[i], mid_y[i]);
				if (dist < min_dist) {
					min_dist = dist;
					newIndex[i] = arc.getIndex();
				}
			}
		}
		return newIndex;
	}

	private float shift(ArcCluster[] clusters1, ArcCluster[] clusters2) {
		float shift = 0;
		for (int i = 0; i < clusters1.length; i++) {
			Point2D c1 = clusters1[i].getCentroidPoint();
			Point2D c2 = clusters2[i].getCentroidPoint();

			shift += c1.distance(c2);
		}

		return shift;
	}
}
